Potężna tablica

Limit pamięci: 128 MB

Dana jest tablica liczb naturalnych . Rozważmy fragment tej tablicy od -tego do -tego elementu: . Oznaczmy przez liczbę wystąpień liczby w tym fragmencie. Potęgą fragmentu tablicy nazywamy sumę iloczynów po wszystkich liczbach naturalnych . Oblicz potęgi podanych fragmentów.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i () oznaczające długość tablicy oraz liczbę fragmentów, dla których należy obliczyć potęgi. Drugi wiersz zawiera liczb naturalnych (). Każdy z kolejnych wierszy opisuje jednen fragment. Opis fragmentu składa się z dwóch liczb całkowitych , (), które oznaczają indeks jego lewego i prawego krańca.

Wyjście

Przykład

Dla danych wejściowych:

8 3
4 3 1 1 1 3 1 2
2 7
1 6
3 8

poprawną odpowiedzią jest:

28
25
21